package listbyorder.access301_400.test395;

public class Solution2 {

    // 解法二 ： 分治加递归 （100%的时间复杂度）
    public int longestSubstring(String s, int k) {
        if (k > s.length()) return 0;
        if (k < 2) return s.length();
        return dg(s.toCharArray(), k, 0, s.length() - 1);
    }

    private int dg(char[] chars, int k, int l, int r) {
        if (r - l + 1 < k) return 0;
        int[] record = new int[26];
        for (int i = l; i <= r; i++) {
            record[chars[i] - 'a']++;
        }

        // 将左边和右边的数都向里面缩
        while (r - l + 1 >= k && record[chars[l] - 'a'] < k) {
            l++;
        }
        while (r - l + 1 >= k && record[chars[r] - 'a'] < k) {
            r--;
        }
        if (r - l + 1 < k) return 0;

        for (int i = l + 1; i < r; i++) {
            if (record[chars[i] - 'a'] < k) {
                return Math.max(dg(chars, k, l, i - 1), dg(chars, k, i + 1, r));
            }
        }
        return r - l + 1;
    }
}
